package features.advance.leetcode.tree.medium;

import features.advance.leetcode.tree.model.TreeNode;
import features.advance.leetcode.util.TreeUtil;

import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

/**
 *  剑指 Offer 34. 二叉树中和为某一值的路径
 *
 *  难度：中等
 *
 * 输入一棵二叉树和一个整数，打印出二叉树中节点值的和为输入整数的所有路径。
 * 从树的根节点开始往下一直到叶节点所经过的节点形成一条路径。
 *
 *
 *
 * 示例:
 * 给定如下二叉树，以及目标和 target = 22，
 *
 *               5
 *              / \
 *             4   8
 *            /   / \
 *           11  13  4
 *          /  \    / \
 *         7    2  5   1
 * 返回:
 *
 * [
 *    [5,4,11,2],
 *    [5,8,4,5]
 * ]
 *
 *
 * 提示：
 *
 * 节点总数 <= 10000
 * 注意：本题与主站 113 题相同：https://leetcode-cn.com/problems/path-sum-ii/
 *
 * @author LIN
 * @date 2021-07-15
 */
public class Offer34 {

    public static void main(String[] args) {
        Solution solution = new Solution() {
        };
        int target = 22;
        String arr = "[5,4,8,11,null,13,4,7,2,null,null,5,1]";
        TreeNode root = TreeUtil.stringToTreeNode(arr);

        List<List<Integer>> lists = solution.pathSum(root, target);
        if(lists != null){
            lists.forEach(System.out::println);
        }



    }

    static class Solution {
        List<List<Integer>> list = new LinkedList<List<Integer>>();
        Deque<Integer> path = new LinkedList<>();
        public List<List<Integer>> pathSum(TreeNode root, int target) {
            dfs(root,target);

            return list;
        }

        public void dfs(TreeNode<Integer> root,int target){
            if(root == null){
                return;
            }
            path.offerLast(root.val);
            target -=root.val;
            if(target == 0 && root.left == null && root.right == null){
                list.add(new LinkedList<>(path));
//                path = new LinkedList<>(path);
            }
            dfs(root.left,target);
            dfs(root.right,target);
            path.pollLast();

        }
    }
}
